package sort

//选择排序
//特点：和冒泡排序的不同是每次外循环结束先得到一个本次最小的元素，然后插入到合适位置，减少交换次数
//时间O(N^2),空间O(1) 不稳定
func SelectionSort(arr []int) []int {
	arrLen := len(arr)
	if arrLen == 0 {
		return arr
	}

	for i := 0; i < arrLen; i++ {
		min := i //假设第一个元素是最小的。仅记录索引
		for j := i + 1; j < arrLen; j++ {
			//Tips: 如果需要从大到小，这里小于号改成大于号即可
			if arr[j] < arr[min] {
				min = j
			}
		}

		//如果值不相等，说明出现了更小的值: 交换
		if min != i {
			arr[min], arr[i] = arr[i], arr[min]
		}
	}

	return arr
}
